import math

# 码长
def code_length():
    list_code = list(code)
    for i in range(len(list_code)):
        k.append(len(code[s[i]]))
    print('码长：{}'.format(k))

def Hx():
    global H
    for i in range(len(s)):
        H += w[i] * math.log(w[i], 2) * (-1)
    # print(round(H, 2))


# 平均码长
def huffmanCode(root, tree, rootCode='', codeDict={}, depth=1, res=0):
    # 对左子树进行处理：如果是叶子节点，就打印编码；否则递归
    if len(root['left'][0]) == 1:
        codeDict[root['left'][0]] = '0' + rootCode
        res += (len(rootCode) + 1) * root['left'][1]  # 计算平均位数
    else:
        codeDict, res = huffmanCode(tree[root['left'][0]], tree, '0' + rootCode, codeDict, depth + 1, res)

    # 对右子树进行处理：如果是叶子节点，就打印编码；否则递归
    if len(root['right'][0]) == 1:
        codeDict[root['right'][0]] = '1' + rootCode
        res += (len(rootCode) + 1) * root['right'][1]  # 计算平均位数
    else:
        codeDict, res = huffmanCode(tree[root['right'][0]], tree, '1' + rootCode, codeDict, depth + 1, res)

    return codeDict, res


s = eval(input('若干字符：'))
w = eval(input('对应概率：'))

# 合并成一个字典
arr = [[s[i], w[i]] for i in range(len(s))]

tree = {}
while len(arr) > 1:
    # 1 根据权重排序
    arr.sort(key=lambda x: x[1])

    # 2 选出最小的两个节点，分别作为左子树，右子树
    l = arr[0]  # 较小的作为左子树
    r = arr[1]  # 较大者作为右子树

    if len(arr) > 2:
        tree[l[0] + r[0]] = {'left': l, 'right': r}

        # 3 用新节点置换这两个节点
        arr = arr[2:]
        arr.append([l[0] + r[0], l[1] + r[1]])
    else:
        tree['root'] = {'left': l, 'right': r}
        break

code, res = huffmanCode(tree['root'], tree)
# 码长k
k = []
H = 0
code_length()
print('平均码长：{:.3}'.format(res/sum(w)))
Hx()
# 码字m
m = []
for i in range(len(s)):
    x = str(code[s[i]].replace('1','2'))
    y = x.replace('0','1')
    z = y.replace('2','0')
    n = list(z)
    n.reverse()
    m.append(''.join(n))
print('码字：{}'.format(m))
print('编码效率：{:.2%}'.format(H / round(res/sum(w),3)))

# 'a','b','c','d'
# 0.4,0.3,0.2,0.1
